// 给定两个整数数组nums1，nums2，要求：计算两个数组中公共的，长度最长的子数组长度

// 思路， 二维dp，用二维数组dp[i][j]表示以nums1[i-1], nums2[j-1]结尾的数组的最长公共子数组的长度
// 如果nums1[i-1] === nums2[j-1] ，则 dp[i][j] = dp[i-1][j-1] + 1

// 时间复杂度：O(n * m)
// 空间复杂度：O(n * m)
function findLength(arr1, arr2) {
    const dp = new Array(arr1.length + 1).fill(0).map(_ => new Array(arr2.length + 1).fill(0))
    let result= 0
    for (let i = 1; i <= arr1.length; i++) {
        for (let j = 1; j <= arr2.length; j++) {
            if (arr1[i - 1] === arr2[j - 1]) {
                dp[i][j] = dp[i-1][j-1] + 1
                result = Math.max(result, dp[i][j])
            }
        }        
    }
    return result
}

// 思路2， 滚动数组优化，因为dp[i][j]只依赖左上角的值，则可以简化为一维数组，d[j]只依赖dp[j-1]
// 再一个，arr2必须倒序遍历，因为如果正序的话，dp[i-1]会统计多次

// 时间复杂度：O(n * m)
// 空间复杂度：O(min(n, m))
function findLength2(arr1, arr2) {
    const dp = new Array(arr2.length + 1).fill(0)
    let result = 0
    for (let i = 1; i <= arr1.length + 1; i++) {
        for (let j = arr2.length; j >= 1; j--) {
            if (arr1[i - 1] === arr2[j - 1]) {
                dp[j] = dp[j-1] + 1
                result = Math.max(dp[j], result)
            } else {
                dp[j] = 0
            }            
        }        
    }
    return result
}

let nums1 = [1, 2, 3, 2, 1], nums2 = [3, 2, 1, 4, 7]

console.log(findLength(nums1, nums2))

console.log(findLength2(nums1, nums2))